/*
 * $Id: hstack.c 11 2008-06-06 13:46:04Z dtikhonov $
 *
 * hstack.c -- history stack implementation.
 *
 * Hmm... should it be simply an array?
 */

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#include "hstack.h"

struct node {
    struct node *next;
    struct node *prev;
    uint64_t position;
    int idx;
};
typedef struct node node_t;

static inline node_t *node_new(int idx, uint64_t position)
{
    node_t *node = calloc(1, sizeof(*node));
    node->position = position;
    node->idx = idx;
    return node;
}

static inline void node_destroy(node_t * node)
{
    free(node);
    return;
}

typedef struct {
    int max_elems;
    int nelems;
    node_t *root;
    node_t *cur;
} hctx_t;

static void _free_chain(node_t * node)
{
    while (node) {
        node_t *next = node->next;
        node_destroy(node);
        node = next;
    }

    return;
}

static inline void _hstack_debug_print(const hstack_t * stack)
{
    hctx_t *ctx = stack->ctx;
    node_t *n;

    for (n = ctx->root; n; n = n->next)
        printf("%d: 0x%lX\n", n->idx, n->position);

    return;
}

static void _hstack_push(struct hstack *self, uint64_t position)
{
    hctx_t *ctx = self->ctx;

    if (ctx->root) {
        if (ctx->cur->position == position)
            return;

        if (ctx->cur->next)
            self->truncate(self);
        assert(NULL == ctx->cur->next);
        ctx->cur->next = node_new(ctx->cur->idx + 1, position);
        ctx->cur->next->prev = ctx->cur;
        ctx->cur = ctx->cur->next;
    } else {
        ctx->cur = ctx->root = node_new(0, position);
    }

    ++ctx->nelems;

    if (ctx->nelems > ctx->max_elems) {
        assert(ctx->nelems == ctx->max_elems + 1);
        node_t *root = ctx->root;
        ctx->root = root->next;
        root->prev = NULL;
        node_destroy(root);
    }

    return;
}

static bool _hstack_prev(hstack_t * self, uint64_t * pos)
{
    hctx_t *ctx = self->ctx;

    if (NULL == ctx->cur || NULL == ctx->cur->prev)
        return false;

    ctx->cur = ctx->cur->prev;
    *pos = ctx->cur->position;
    return true;
}

static bool _hstack_next(hstack_t * self, uint64_t * pos)
{
    hctx_t *ctx = self->ctx;

    if (NULL == ctx->cur || NULL == ctx->cur->next)
        return false;

    ctx->cur = ctx->cur->next;
    *pos = ctx->cur->position;
    return true;
}

static void _hstack_truncate(hstack_t * self)
{
    hctx_t *ctx = self->ctx;

    if (ctx->cur->next) {
        _free_chain(ctx->cur->next);
        ctx->cur->next = NULL;
        ctx->nelems = ctx->cur->idx + 1;
    }

    return;
}

static void _hstack_destroy(hstack_t * self)
{
    hctx_t *ctx = self->ctx;

    if (ctx->root)
        _free_chain(ctx->root);

    free(ctx);
    free(self);

    return;
}

hstack_t *hstack_new(int max_elems)
{
    hctx_t *ctx = calloc(1, sizeof(*ctx));
    ctx->max_elems = max_elems;

    hstack_t *self = calloc(1, sizeof(*self));
    self->ctx = ctx;

    self->push = _hstack_push;
    self->prev = _hstack_prev;
    self->next = _hstack_next;
    self->truncate = _hstack_truncate;
    self->destroy = _hstack_destroy;

    return self;
}
